#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

int dfs(TreeNode* root, int val)
{
    if (root == nullptr) return 0;
    val = (val << 1) | root->val;
    if (root->left == nullptr && root->right == nullptr)
        return val;
    return dfs(root->left, val) + dfs(root->right, val);
}
int sumRootToLeaf(TreeNode* root)
{
    return dfs(root, 0);
}

int itsumRootToLeaf(TreeNode* root)
{
    int ans = 0, sum = 0;
    stack<TreeNode*> st;
    TreeNode* pre = nullptr;
    while (root || !st.empty())
    {
        while (root)
        {
            sum = (sum << 1) | root->val;
            st.push(root);
            root = root->left;
        }
        root = st.top();

        if (root->right == nullptr || root->right == pre)
        {
            if (root->right == nullptr && root->left == nullptr)
                ans += sum;
            sum >>= 1;
            st.pop();
            pre = root;
            root = nullptr;
        }
        else
            root = root->right;
    }
    return ans;
}

class Solution {
public:
    int ans = 0;
    int dfs1(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int sumleft = dfs1(root->left);
        int sumright = dfs1(root->right);
        ans += abs(sumright - sumleft);
        return sumleft + sumright + root->val;
    }
    int findTilt(TreeNode* root) {
        dfs1(root);
        return ans;
    }

    int dfs2(TreeNode* root, int val)
    {
        val = val * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) return val;
        int ret = 0;
        if (root->left) ret += dfs2(root->left, val);
        if (root->right) ret += dfs2(root->right, val);
        return ret;
    }
    int sumNumbers(TreeNode* root) {
        return dfs2(root, 0);
    }

    struct ListNode
    {
        int val;
        ListNode* next;
        ListNode():val(0), next(nullptr){}
        ListNode(int n):val(n),next(nullptr){}
        ListNode(int n,ListNode* next):val(n),next(next){}
    };

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1)
            return l2;
        if (!l2)
            return l1;
        if (l1->val > l2->val)
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
        else
        {
            l1->next = mergeTwoLists(l2, l1->next);
            return l1;
        }
    }

    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }
    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        if (n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        dfs(A, C, B, n - 1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B, A, C, n - 1);
    }
};